package sort.shellsort;

/**
 * 希尔排序
 *
 * @author xushijian
 * @date 2021/12/20 17:06
 */
public class ShellSort {

    public static void main(String[] args) {

        int[] arr = {100,6, 4, 5, 7,1000,51, 21, 8, 11, 0, 9, 1};

        shellSort(arr);
        for (int i : arr) {
            System.out.println(i);
        }

    }

    public static void shellSort1(int[] arr) {

        if (arr == null || arr.length <= 1) {
            return;
        }

        int arrNum = arr.length;
        int tmp, j;
        j = arrNum / 2;
        //单组比较并交换
        for (int i = 0; i <= arrNum / 2; i++) {
            tmp = arr[i];
            if (tmp > arr[j + i]) {
                arr[i] = arr[j + i];
                arr[j + 1] = tmp;
            }
        }

        //奇数比较、偶数比较

        //插入排序

    }


    public static void shellSort(int[] arr) {

        if (arr == null || arr.length <= 1) {
            return;
        }

        int len = arr.length, tmp, j;
        //增量gap=length/2，缩小增量继续以gap = gap/2的方式，
        // 这种增量选择我们可以用一个序列来表示，{n/2, (n/2)/2, …, 1}，称为增量序列。
        for (int gap = len / 2; gap >= 1; gap = gap / 2) {
            for (int i = gap; i < len; i++) {
                tmp = arr[i];
                j = i - gap;
                while (j >= 0 && arr[j] > tmp) {
                    arr[j + gap] = arr[j];
                    j = j - gap;
                }
                arr[j + gap] = tmp;
            }

        }

    }
}